SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Linear complementarity problem</title>

</head>

Linear complementarity problem

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In mathematical <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization theory</a>, the linear complementarity problem (LCP) arises frequently in <a href="Computational_mechanics" title="Computational mechanics">computational mechanics</a> and encompasses the well-known <a href="Quadratic_programming" title="Quadratic programming">quadratic programming</a> as a special case. It was proposed by Cottle and <a href="George_Dantzig" title="George Dantzig">Dantzig</a> in 1968.<a href="#cite_note-FOOTNOTEMurty1988-1">[1]</a><a href="#cite_note-FOOTNOTECottlePangStone1992-2">[2]</a><a href="#cite_note-FOOTNOTECottleDantzig1968-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Formulation">Formulation</h2></div>

Given a <a href="Matrix_(mathematics)" title="Matrix (mathematics)">real matrix</a> M and <a href="Vector_space" title="Vector space">vector</a> q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w,z\geqslant 0,}</annotation>

</semantics>

</math><img src="./a404f64c68cbd7f4e57cb6c8889c4772341af8c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.694ex; height:2.509ex;" alt="{\displaystyle w,z\geqslant 0,}" loading="lazy"> (that is, each component of these two vectors is <a href="Sign_(mathematics)" title="Sign (mathematics)">non-negative</a>)</li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z^{T}w=0}</annotation>

</semantics>

</math><img src="./f4c1940bf857f8e3ff3aa01eb47711cad2e1221a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.405ex; height:2.676ex;" alt="{\displaystyle z^{T}w=0}" loading="lazy"> or equivalently <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}</annotation>

</semantics>

</math><img src="./71c3c8485f597f25141ec0f58acc767f7a45ef3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:13.794ex; height:3.843ex;" alt="{\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}" loading="lazy"> This is the <a href="Complementarity_theory" title="Complementarity theory">complementarity</a> condition, since it implies that, for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, at most one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>

</semantics>

</math><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{i}}</annotation>

</semantics>

</math><img src="./5c6e920bac39ad09fff4efef16254595091a1025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.881ex; height:2.009ex;" alt="{\displaystyle z_{i}}" loading="lazy"> can be positive.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=Mz+q}</annotation>

</semantics>

</math><img src="./5ff5997ddce611f4747ea4adb3bc6120eca92d81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.203ex; height:2.509ex;" alt="{\displaystyle w=Mz+q}" loading="lazy"></li></ul>

A sufficient condition for existence and uniqueness of a solution to this problem is that M be <a href="Symmetric_matrix" title="Symmetric matrix">symmetric</a> <a href="Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">positive-definite</a>. If M is such that LCP(q, M) has a solution for every q, then M is a <a href="Q-matrix" title="Q-matrix">Q-matrix</a>. If M is such that LCP(q, M) have a unique solution for every q, then M is a <a href="P-matrix" title="P-matrix">P-matrix</a>. Both of these characterizations are sufficient and necessary.<a href="#cite_note-FOOTNOTEMurty1972-4">[4]</a>

The vector w is a <a href="Slack_variable" title="Slack variable">slack variable</a>,<a href="#cite_note-FOOTNOTETaylor2015[httpsbooksgooglecombooksidJBdoBgAAQBAJpgPA172_172]-5">[5]</a> and so is generally discarded after z is found. As such, the problem can also be formulated as:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Mz+q\geqslant 0}</annotation>

</semantics>

</math><img src="./7132a23cb211e062680ecbd880787c8dcab8c2f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.701ex; height:2.509ex;" alt="{\displaystyle Mz+q\geqslant 0}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\geqslant 0}</annotation>

</semantics>

</math><img src="./39fdfd8336f48d9f2cd7240b3a7bd98f576f03c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.349ex; height:2.343ex;" alt="{\displaystyle z\geqslant 0}" loading="lazy"></li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z^{\mathrm {T} }(Mz+q)=0}</annotation>

</semantics>

</math><img src="./3d1620e24638a5582789c4fc5cfd978ad45677ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.02ex; height:3.176ex;" alt="{\displaystyle z^{\mathrm {T} }(Mz+q)=0}" loading="lazy"> (the complementarity condition)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Convex_quadratic-minimization:_Minimum_conditions">Convex quadratic-minimization: Minimum conditions</h2></div>

Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(z)=z^{T}(Mz+q)}</annotation>

</semantics>

</math><img src="./f6ec3ddaf6fa289e872e0c17198ae74f27cb5700.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.004ex; height:3.176ex;" alt="{\displaystyle f(z)=z^{T}(Mz+q)}" loading="lazy"></dd></dl>

subject to the constraints

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {Mz}+q\geqslant 0}</annotation>

</semantics>

</math><img src="./9fed112395b95a6656dc62bc2e619a989958c039.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.701ex; height:2.509ex;" alt="{\displaystyle {Mz}+q\geqslant 0}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\geqslant 0}</annotation>

</semantics>

</math><img src="./39fdfd8336f48d9f2cd7240b3a7bd98f576f03c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.349ex; height:2.343ex;" alt="{\displaystyle z\geqslant 0}" loading="lazy"></dd></dl>

These constraints ensure that f is always non-negative. The minimum of f is 0 at z if and only if z solves the linear complementarity problem.

If M is <a href="Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">positive definite</a>, any algorithm for solving (strictly) convex <a href="Quadratic_programming" title="Quadratic programming">QPs</a> can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as <a href="Lemke's_algorithm" title="Lemke's algorithm">Lemke's algorithm</a> and a variant of the <a href="Simplex_algorithm" title="Simplex algorithm">simplex algorithm of Dantzig</a> have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice.

Also, a quadratic-programming problem stated as minimize <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}">

<msup>

</mrow>

</msup>

<mfrac>

</mfrac>

</mstyle>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}</annotation>

</semantics>

</math><img src="./7e7ba05ea5ee53b23246108e9e71f1f388087e4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:21.627ex; height:3.509ex;" alt="{\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}" loading="lazy"> subject to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ax\geqslant b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax\geqslant b}</annotation>

</semantics>

</math><img src="./8c9af3a1d71a66e972626ad0be36b8eaf3b2cf54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.169ex; height:2.343ex;" alt="{\displaystyle Ax\geqslant b}" loading="lazy"> as well as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geqslant 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geqslant 0}</annotation>

</semantics>

</math><img src="./ac393553034a1b76077c3e5147ced1b30fec12a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geqslant 0}" loading="lazy"> with Q symmetric

is the same as solving the LCP with

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./f39be493b7191b3a3d40ab032f432b2b1b39b36c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:33.708ex; height:6.176ex;" alt="{\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}" loading="lazy"></dd></dl>

This is because the <a href="Karush%E2%80%93Kuhn%E2%80%93Tucker" class="mw-redirect" title="Karush–Kuhn–Tucker">Karush–Kuhn–Tucker</a> conditions of the QP problem can be written as:

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}</annotation>

</semantics>

</math><img src="./62fd73c084c38146544c564c8dc9072143d1b5a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.171ex; width:21.387ex; height:11.509ex;" alt="{\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}" loading="lazy"></dd></dl>

with v the Lagrange multipliers on the non-negativity constraints, λ the multipliers on the inequality constraints, and s the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables (x, s) with its set of KKT vectors (optimal Lagrange multipliers) being (v, λ). In that case,

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./78d83ac227727386d4e91157502e40237f5f3ac9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:23.524ex; height:6.176ex;" alt="{\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}" loading="lazy"></dd></dl>

If the non-negativity constraint on the x is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as Q is non-singular (which is guaranteed if it is <a href="Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">positive definite</a>). The multipliers v are no longer present, and the first KKT conditions can be rewritten as:

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Qx=A^{T}{\lambda }-c}</annotation>

</semantics>

</math><img src="./5b176208ecc766163ce2b6e3d59bddedad8d9a44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.601ex; height:3.009ex;" alt="{\displaystyle Qx=A^{T}{\lambda }-c}" loading="lazy"></dd></dl>

or:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}</annotation>

</semantics>

</math><img src="./ce85099d559f2c0b3c4f4a09600550143de92bf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.743ex; height:3.176ex;" alt="{\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}" loading="lazy"></dd></dl>

pre-multiplying the two sides by A and subtracting b we obtain:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}</annotation>

</semantics>

</math><img src="./d9b5134ceaeb733ca90b42145bd07d4aadadaf11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.293ex; height:3.176ex;" alt="{\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}" loading="lazy"></dd></dl>

The left side, due to the second KKT condition, is s. Substituting and reordering:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}</annotation>

</semantics>

</math><img src="./7ddedac0b15595f28fc9920841eaf645aa6cebbb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.004ex; height:3.176ex;" alt="{\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}" loading="lazy"></dd></dl>

Calling now

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}</annotation>

</semantics>

</math><img src="./7d7522d801fbff5fd7624e45d767bd0fa690ae2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:21.315ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}" loading="lazy"></dd></dl>

we have an LCP, due to the relation of complementarity between the slack variables s and their Lagrange multipliers λ. Once we solve it, we may obtain the value of x from λ through the first KKT condition.

Finally, it is also possible to handle additional equality constraints:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{eq}x=b_{eq}}</annotation>

</semantics>

</math><img src="./5ec0f66a0c14f871c5988be8954efa6d6739dacd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.678ex; height:2.843ex;" alt="{\displaystyle A_{eq}x=b_{eq}}" loading="lazy"></dd></dl>

This introduces a vector of Lagrange multipliers μ, with the same dimension as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{eq}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{eq}}</annotation>

</semantics>

</math><img src="./37076240c3e22eeb10fb8659623456f34bed8f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.752ex; height:2.843ex;" alt="{\displaystyle b_{eq}}" loading="lazy">.

It is easy to verify that the M and Q for the LCP system <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=M{\lambda }+Q}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=M{\lambda }+Q}</annotation>

</semantics>

</math><img src="./362e2c248a4c29249774d1770e9adc409c0488a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.665ex; height:2.509ex;" alt="{\displaystyle s=M{\lambda }+Q}" loading="lazy"> are now expressed as:

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}</annotation>

</semantics>

</math><img src="./162443b3e671897b48b647debbf3be9746c3b1b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.267ex; margin-bottom: -0.237ex; width:42.483ex; height:14.176ex;" alt="{\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}" loading="lazy"></dd></dl>

From λ we can now recover the values of both x and the Lagrange multiplier of equalities μ:

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./ef0058c49d0969225174fb447f4edd2461c62054.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.439ex; margin-bottom: -0.233ex; width:35.913ex; height:7.009ex;" alt="{\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}" loading="lazy"></dd></dl>

In fact, most QP solvers work on the LCP formulation, including the <a href="Interior_point_method" class="mw-redirect" title="Interior point method">interior point method</a>, principal / complementarity pivoting, and <a href="Active_set" class="mw-redirect" title="Active set">active set</a> methods.<a href="#cite_note-FOOTNOTEMurty1988-1">[1]</a><a href="#cite_note-FOOTNOTECottlePangStone1992-2">[2]</a> LCP problems can be solved also by the <a href="Criss-cross_algorithm" title="Criss-cross algorithm">criss-cross algorithm</a>,<a href="#cite_note-FOOTNOTEFukudaNamiki1994-6">[6]</a><a href="#cite_note-FOOTNOTEFukudaTerlaky1997-7">[7]</a><a href="#cite_note-FOOTNOTEden_HertogRoosTerlaky1993-8">[8]</a><a href="#cite_note-FOOTNOTECsizmadiaIllés2006-9">[9]</a> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<a href="#cite_note-FOOTNOTEden_HertogRoosTerlaky1993-8">[8]</a><a href="#cite_note-FOOTNOTECsizmadiaIllés2006-9">[9]</a> A sufficient matrix is a generalization both of a <a href="Positive-definite_matrix" class="mw-redirect" title="Positive-definite matrix">positive-definite matrix</a> and of a <a href="P-matrix" title="P-matrix">P-matrix</a>, whose <a href="Principal_minor" class="mw-redirect" title="Principal minor">principal minors</a> are each positive.<a href="#cite_note-FOOTNOTEden_HertogRoosTerlaky1993-8">[8]</a><a href="#cite_note-FOOTNOTECsizmadiaIllés2006-9">[9]</a><a href="#cite_note-FOOTNOTECottlePangVenkateswaran1989-10">[10]</a>

Such LCPs can be solved when they are formulated abstractly using <a href="Oriented_matroid" title="Oriented matroid">oriented-matroid</a> theory.<a href="#cite_note-FOOTNOTETodd1985-11">[11]</a><a href="#cite_note-FOOTNOTETerlakyZhang1993-12">[12]</a><a href="#cite_note-FOOTNOTEBjörnerLas_VergnasSturmfelsWhite1999-13">[13]</a>

<ul><li><a href="Complementarity_theory" title="Complementarity theory">Complementarity theory</a></li>

<li><a href="Physics_engine" title="Physics engine">Physics engine</a> Impulse/constraint type physics engines for games use this approach.</li>

<li><a href="Contact_dynamics" title="Contact dynamics">Contact dynamics</a> Contact dynamics with the nonsmooth approach.</li>

<li><a href="Bimatrix_game" title="Bimatrix game">Bimatrix games</a> can be reduced to LCP.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 24em;">

<li id="cite_note-FOOTNOTEMurty1988-1">^ <a href="#cite_ref-FOOTNOTEMurty1988_1-0">a</a> <a href="#cite_ref-FOOTNOTEMurty1988_1-1">b</a> <a href="#CITEREFMurty1988">Murty (1988)</a>.

</li>

<li id="cite_note-FOOTNOTECottlePangStone1992-2">^ <a href="#cite_ref-FOOTNOTECottlePangStone1992_2-0">a</a> <a href="#cite_ref-FOOTNOTECottlePangStone1992_2-1">b</a> <a href="#CITEREFCottlePangStone1992">Cottle, Pang & Stone (1992)</a>.

</li>

<li id="cite_note-FOOTNOTECottleDantzig1968-3"><a href="#cite_ref-FOOTNOTECottleDantzig1968_3-0">^</a> <a href="#CITEREFCottleDantzig1968">Cottle & Dantzig (1968)</a>.

</li>

<li id="cite_note-FOOTNOTEMurty1972-4"><a href="#cite_ref-FOOTNOTEMurty1972_4-0">^</a> <a href="#CITEREFMurty1972">Murty (1972)</a>.

</li>

<li id="cite_note-FOOTNOTETaylor2015[httpsbooksgooglecombooksidJBdoBgAAQBAJpgPA172_172]-5"><a href="#cite_ref-FOOTNOTETaylor2015[httpsbooksgooglecombooksidJBdoBgAAQBAJpgPA172_172]_5-0">^</a> <a href="#CITEREFTaylor2015">Taylor (2015)</a>, p. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172">172</a>.

</li>

<li id="cite_note-FOOTNOTEFukudaNamiki1994-6"><a href="#cite_ref-FOOTNOTEFukudaNamiki1994_6-0">^</a> <a href="#CITEREFFukudaNamiki1994">Fukuda & Namiki (1994)</a>.

</li>

<li id="cite_note-FOOTNOTEFukudaTerlaky1997-7"><a href="#cite_ref-FOOTNOTEFukudaTerlaky1997_7-0">^</a> <a href="#CITEREFFukudaTerlaky1997">Fukuda & Terlaky (1997)</a>.

</li>

<li id="cite_note-FOOTNOTEden_HertogRoosTerlaky1993-8">^ <a href="#cite_ref-FOOTNOTEden_HertogRoosTerlaky1993_8-0">a</a> <a href="#cite_ref-FOOTNOTEden_HertogRoosTerlaky1993_8-1">b</a> <a href="#cite_ref-FOOTNOTEden_HertogRoosTerlaky1993_8-2">c</a> <a href="#CITEREFden_HertogRoosTerlaky1993">den Hertog, Roos & Terlaky (1993)</a>.

</li>

<li id="cite_note-FOOTNOTECsizmadiaIllés2006-9">^ <a href="#cite_ref-FOOTNOTECsizmadiaIllés2006_9-0">a</a> <a href="#cite_ref-FOOTNOTECsizmadiaIllés2006_9-1">b</a> <a href="#cite_ref-FOOTNOTECsizmadiaIllés2006_9-2">c</a> <a href="#CITEREFCsizmadiaIllés2006">Csizmadia & Illés (2006)</a>.

</li>

<li id="cite_note-FOOTNOTECottlePangVenkateswaran1989-10"><a href="#cite_ref-FOOTNOTECottlePangVenkateswaran1989_10-0">^</a> <a href="#CITEREFCottlePangVenkateswaran1989">Cottle, Pang & Venkateswaran (1989)</a>.

</li>

<li id="cite_note-FOOTNOTETodd1985-11"><a href="#cite_ref-FOOTNOTETodd1985_11-0">^</a> <a href="#CITEREFTodd1985">Todd (1985)</a>.

</li>

<li id="cite_note-FOOTNOTETerlakyZhang1993-12"><a href="#cite_ref-FOOTNOTETerlakyZhang1993_12-0">^</a> <a href="#CITEREFTerlakyZhang1993">Terlaky & Zhang (1993)</a>.

</li>

<li id="cite_note-FOOTNOTEBjörnerLas_VergnasSturmfelsWhite1999-13"><a href="#cite_ref-FOOTNOTEBjörnerLas_VergnasSturmfelsWhite1999_13-0">^</a> <a href="#CITEREFBjörnerLas_VergnasSturmfelsWhite1999">Björner et al. (1999)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBjörnerLas_VergnasSturmfelsWhite1999" class="citation book cs1"><a href="Anders_Bj%C3%B6rner" title="Anders Björner">Björner, Anders</a>; <a href="Michel_Las_Vergnas" title="Michel Las Vergnas">Las Vergnas, Michel</a>; <a href="Bernd_Sturmfels" title="Bernd Sturmfels">Sturmfels, Bernd</a>; <a href="Neil_White" class="mw-redirect" title="Neil White">White, Neil</a>; <a href="G%C3%BCnter_M._Ziegler" title="Günter M. Ziegler">Ziegler, Günter</a> (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511586507">10.1017/CBO9780511586507</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-77750-6</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1744046">1744046</a>.</cite></li>

<li><cite id="CITEREFCottleDantzig1968" class="citation journal cs1">Cottle, R. W.; <a href="G._B._Dantzig" class="mw-redirect" title="G. B. Dantzig">Dantzig, G. B.</a> (1968). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2868%2990052-9">"Complementary pivot theory of mathematical programming"</a>. Linear Algebra and Its Applications. 1: 103–125. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2868%2990052-9">10.1016/0024-3795(68)90052-9</a>.</cite></li>

<li><cite id="CITEREFCottlePangStone1992" class="citation book cs1">Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc. pp. xxiv+762 pp. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-12-192350-1</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1150683">1150683</a>.</cite></li>

<li><cite id="CITEREFCottlePangVenkateswaran1989" class="citation journal cs1 cs1-prop-long-vol"><a href="Richard_W._Cottle" title="Richard W. Cottle">Cottle, R. W.</a>; Pang, J.-S.; Venkateswaran, V. (March–April 1989). "Sufficient matrices and the linear complementarity problem". Linear Algebra and Its Applications. 114–115: 231–249. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2889%2990463-1">10.1016/0024-3795(89)90463-1</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0986877">0986877</a>.</cite></li>

<li><cite id="CITEREFCsizmadiaIllés2006" class="citation journal cs1">Csizmadia, Zsolt; Illés, Tibor (2006). <a rel="nofollow" class="external text" href="http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf">"New criss-cross type algorithms for linear complementarity problems with sufficient matrices"</a> (PDF). Optimization Methods and Software. 21 (2): 247–266. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F10556780500095009">10.1080/10556780500095009</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:24418835">24418835</a>.</cite></li>

<li><cite id="CITEREFFukudaNamiki1994" class="citation journal cs1"><a href="Komei_Fukuda" title="Komei Fukuda">Fukuda, Komei</a>; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01582581">10.1007/BF01582581</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1286455">1286455</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21476636">21476636</a>.</cite></li>

<li><cite id="CITEREFFukudaTerlaky1997" class="citation journal cs1">Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3): 369–395. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.9373">10.1.1.36.9373</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02614325">10.1007/BF02614325</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1464775">1464775</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2794181">2794181</a>. <a rel="nofollow" class="external text" href="http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps">Postscript preprint</a>.</cite></li>

<li><cite id="CITEREFden_HertogRoosTerlaky1993" class="citation journal cs1">den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). <a rel="nofollow" class="external text" href="http://core.ac.uk/download/pdf/6714737.pdf">"The linear complementarity problem, sufficient matrices, and the criss-cross method"</a> (PDF). Linear Algebra and Its Applications. 187: 1–14. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2893%2990124-7">10.1016/0024-3795(93)90124-7</a>.</cite></li>

<li><cite id="CITEREFMurty1972" class="citation journal cs1">Murty, Katta G. (January 1972). <a rel="nofollow" class="external text" href="https://deepblue.lib.umich.edu/bitstream/2027.42/34188/1/0000477.pdf">"On the number of solutions to the complementarity problem and spanning properties of complementary cones"</a> (PDF). Linear Algebra and Its Applications. 5 (1): 65–108. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2872%2990019-5">10.1016/0024-3795(72)90019-5</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2027.42%2F34188">2027.42/34188</a>.</cite></li>

<li><cite id="CITEREFMurty1988" class="citation book cs1">Murty, K. G. (1988). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/">Linear complementarity, linear and nonlinear programming</a>. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-88538-403-8</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0949214">0949214</a>. <a rel="nofollow" class="external text" href="http://www-personal.umich.edu/~murty/">Updated and free PDF version at Katta G. Murty's website</a>. Archived from <a rel="nofollow" class="external text" href="http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/">the original</a> on 2010-04-01.</cite></li>

<li><cite id="CITEREFTaylor2015" class="citation book cs1">Taylor, Joshua Adam (2015). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=JBdoBgAAQBAJ">Convex Optimization of Power Systems</a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781107076877</bdi>.</cite></li>

<li><cite id="CITEREFTerlakyZhang1993" class="citation journal cs1 cs1-prop-long-vol">Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1): 203–233. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7658">10.1.1.36.7658</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02096264">10.1007/BF02096264</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0254-5330">0254-5330</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1260019">1260019</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6058077">6058077</a>.</cite></li>

<li><cite id="CITEREFTodd1985" class="citation journal cs1">Todd, Michael J. (1985). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2885%2990042-5">"Linear and quadratic programming in oriented matroids"</a>. Journal of Combinatorial Theory. Series B. 39 (2): 105–133. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2885%2990042-5">10.1016/0095-8956(85)90042-5</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0811116">0811116</a>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFR._Chandrasekaran" class="citation web cs1">R. Chandrasekaran. <a rel="nofollow" class="external text" href="http://www.utdallas.edu/~chandra/documents/6311/bimatrix.pdf">"Bimatrix games"</a> (PDF). pp. 5–7. Retrieved 18 December 2015.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20041029022008/http://www.american.edu/econ/gaussres/optimize/quadprog.src">LCPSolve</a> — A simple procedure in GAUSS to solve a linear complementarity problem</li>

<li><a href="Siconos" title="Siconos">Siconos</a>/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Complementarity_problems_and_algorithms137" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Complementarity_problems_and_algorithms137" style="font-size:114%;margin:0 4em"><a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)"> Complementarity problems and algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Complementarity Problems</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Linear_programming" title="Linear programming"> Linear programming (LP)</a></li>

<li><a href="Quadratic_programming" title="Quadratic programming"> Quadratic programming (QP)</a></li>

<li><a href="Mixed_linear_complementarity_problem" title="Mixed linear complementarity problem"> Mixed linear (MLCP)</a></li>

<li><a href="Mixed_complementarity_problem" title="Mixed complementarity problem"> Mixed (MCP)</a></li>

<li><a href="Nonlinear_complementarity_problem" title="Nonlinear complementarity problem"> Nonlinear (NCP)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis</a>-<a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0;line-height:1.4em; padding:0.33em 0;"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex</a> (<a href="George_Dantzig" title="George Dantzig">Dantzig</a>)</li>

<li><a href="Revised_simplex_algorithm" class="mw-redirect" title="Revised simplex algorithm">Revised simplex</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Lemke</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-15" href="https://en.wikipedia.org/wiki/?title=Linear_complementarity_problem&oldid=1300598077">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>